//add other people'sc comment
F[l1][u1][l2][u2]表示s1的[l1, u1]是否能通过scramble得到s2的[l2, u2]

则如果存在k，使得要么

1. F[l1][l1 + k - 1][l2][l2 + k - 1] &&
   F[l1 + k][u1][l2 + k][u2]

2. F[l1][l1 + k - 1][u2 - k + 1][u2] &&
   F[l1 + k][u1][l2][l2 + k - 1]

两者有一个真，则F[l1][u1][l2][u2]为真

因为l1, u1, l2确定，则u2 = u1 - l1 + l2，所以状态总数为n^3

决策为o(n), 总复杂度o(N^4) */

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;


bool isScrambleHelper(const string &s1, const string &s2,  map<pair<string, string>, bool> &myMap)
{
    pair<string, string> key = make_pair(s1, s2);
	cout << s1 << " " << s2 << endl;
    if (myMap.count(key) != 0) return myMap[key];
    bool result = false;
    if (s1 == s2)
        result = true;
	else if (s1.size() == 0 || s2.size() == 0) {
		result = false;
	}  else if (s1.size() != s2.size() ) {
		result = false;
	} else { 
    for (int i = 1; i < s1.size(); i++) {
            if ((isScrambleHelper(s1.substr(0, i), s2.substr(0,i),myMap) && isScrambleHelper(s1.substr(i, s1.size()-i), s2.substr(i, s2.size()-i), myMap)) ||
                (isScrambleHelper(s1.substr(0, i), s2.substr(s2.size()-i,i),myMap) && isScrambleHelper(s1.substr(i, s1.size()-i),  s2.substr(0,s1.size()-i), myMap))) {
					result = true;
					break;
            }
    }
    }
    myMap[key] = result;
	cout << s1 << " " << s2 << result;
    return result;
}


class Solution {
    public:
        bool isScramble(string s1, string s2) {
             map<pair<string, string>, bool> myMap;
             return isScrambleHelper(s1, s2, myMap);  
        }
};

int main(int argc, char **argv)
{
    Solution mySolution;
    cout << "-----------------Test 1--------------------" << endl;
	bool result =  mySolution.isScramble("eat", "tae");
	cout << endl;
    cout << result << endl;

    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
